package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC403 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public boolean canCross(int[] stones) {
            if (null == stones || stones.length <= 1) return true;
            if (stones.length >= 2 && stones[1] != 1) return false;

            int len = stones.length;
            Set<Integer>[] dp = new HashSet[stones.length];
            dp[1] = new HashSet<>(Arrays.asList(1));

            for (int i = 2; i < stones.length; i++) {
                dp[i] = new HashSet<>();
                for (int k = 1; k < i; k++) {
                    int lengthIK = stones[i] - stones[k];
                    if (dp[k].contains(lengthIK - 1) || dp[k].contains(lengthIK) || dp[k].contains(lengthIK + 1))
                        dp[i].add(lengthIK);
                }
            }

            return dp[len - 1].size() > 0;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[0,2,4,5,6,8,9,11,14,17,18,19,20,22,23,24,25,27,30]");
        System.out.println(solution.canCross(arr));
    }

    public static void main(String[] args) throws Exception {
        LC403 an = new LC403();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
